class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        ans = []
        path = [0] * n          #保存当前正在构建的排列
        used = [False] * n      #标记 nums 中的元素是否已被使用
        def dfs(i):
            if i == n:
                ans.append(path.copy())     
                return 
            for j in range(n):
                if not used[j]:
                    path[i] = nums[j]
                    used[j] = True
                    dfs(i+1)
                    used[j] = False
            
        dfs(0)
        return ans